package leetcode

import "math"

// Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// https://leetcode.com/problems/binary-tree-maximum-path-sum/
func maxPathSum(root *TreeNode) int {
	res := math.MinInt
	maxSum(root, &res)
	return res
}

func maxSum(root *TreeNode, res *int) int {
	if root == nil {
		return 0
	}
	left := max(maxSum(root.Left, res), 0)
	right := max(maxSum(root.Right, res), 0)
	if *res < left+right+root.Val {
		*res = left + right + root.Val
	}
	return root.Val + max(left, right)
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

// [-10,9,20,null,null,15,7]
// [3,4,-5,null,null,-1,-3]
